/**
 *   Copyright 2014 Royce Remulla
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package cjcast.y2008.problem;

import java.io.IOException;
import java.util.HashSet;
import java.util.Set;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

import cjcast.common.AbstractSolution;
import cjcast.common.Solution;
import cjcast.y2008.problem.AlwaysTurnLeftHelper.Direction;
import cjcast.y2008.problem.AlwaysTurnLeftHelper.Move;


/**
 * 
 * @see <a
 *      href="http://code.google.com/codejam/contest/32003/dashboard#s=p1">Google
 *      Code Jam page</a><br/>
 * <br/>
 * 
 *      <b>Problem</b><br/>
 * 
 *      You find yourself standing outside of a perfect maze. A maze is defined
 *      as "perfect" if it meets the following conditions:
 * 
 *      It is a rectangular grid of rooms, R rows by C columns. There are
 *      exactly two openings on the outside of the maze: the entrance and the
 *      exit. The entrance is always on the north wall, while the exit could be
 *      on any wall. There is exactly one path between any two rooms in the maze
 *      (that is, exactly one path that does not involve backtracking).
 * 
 *      You decide to solve the perfect maze using the "always turn left"
 *      algorithm, which states that you take the leftmost fork at every
 *      opportunity. If you hit a dead end, you turn right twice (180 degrees
 *      clockwise) and continue. (If you were to stick out your left arm and
 *      touch the wall while following this algorithm, you'd solve the maze
 *      without ever breaking contact with the wall.) Once you finish the maze,
 *      you decide to go the extra step and solve it again (still always turning
 *      left), but starting at the exit and finishing at the entrance.
 * 
 *      The path you take through the maze can be described with three
 *      characters: 'W' means to walk forward into the next room, 'L' means to
 *      turn left (or counterclockwise) 90 degrees, and 'R' means to turn right
 *      (or clockwise) 90 degrees. You begin outside the maze, immediately
 *      adjacent to the entrance, facing the maze. You finish when you have
 *      stepped outside the maze through the exit. For example, if the entrance
 *      is on the north and the exit is on the west, your path through the
 *      following maze would be WRWWLWWLWWLWLWRRWRWWWRWWRWLW:
 * 
 *      If the entrance and exit were reversed such that you began outside the
 *      west wall and finished out the north wall, your path would be
 *      WWRRWLWLWWLWWLWWRWWRWWLW. Given your two paths through the maze
 *      (entrance to exit and exit to entrance), your code should return a
 *      description of the maze.
 * 
 *      Input
 * 
 *      The first line of input gives the number of cases, N. N test cases
 *      follow. Each case is a line formatted as
 * 
 *      entrance_to_exit exit_to_entrance
 * 
 *      All paths will be at least two characters long, consist only of the
 *      characters 'W', 'L', and 'R', and begin and end with 'W'.
 * 
 *      Output
 * 
 *      For each test case, output one line containing "Case #x:" by itself. The
 *      next R lines give a description of the R by C maze. There should be C
 *      characters in each line, representing which directions it is possible to
 *      walk from that room. Refer to the following legend: Character Can walk
 *      north? Can walk south? Can walk west? Can walk east? 1 Yes No No No 2 No
 *      Yes No No 3 Yes Yes No No 4 No No Yes No 5 Yes No Yes No 6 No Yes Yes No
 *      7 Yes Yes Yes No 8 No No No Yes 9 Yes No No Yes a No Yes No Yes b Yes
 *      Yes No Yes c No No Yes Yes d Yes No Yes Yes e No Yes Yes Yes f Yes Yes
 *      Yes Yes
 * 
 *      Limits
 * 
 *      1 ≤ N ≤ 100.
 * 
 *      Small dataset
 * 
 *      2 ≤ len(entrance_to_exit) ≤ 100, 2 ≤ len(exit_to_entrance) ≤
 *      100.
 * 
 *      Large dataset
 * 
 *      2 ≤ len(entrance_to_exit) ≤ 10000, 2 ≤ len(exit_to_entrance) ≤
 *      10000.
 * 
 *      Sample
 * 
 *      Input 2 WRWWLWWLWWLWLWRRWRWWWRWWRWLW WWRRWLWLWWLWWLWWRWWRWWLW WW WW
 * 
 *      Output Case #1: ac5 386 9c7 e43 9c5 Case #2: 3
 * 
 * 
 *      <pre>
 * $Author: royce.com@gmail.com $ 
 * $Date: 2015-02-03 03:44:46 +0000 (Tue, 03 Feb 2015) $
 * </pre>
 * 
 * @author r39
 */
public class AlwaysTurnLeft extends AbstractSolution<AlwaysTurnLeftBean> {


    /** Platform independent line separator. */
    static final String LINE_SEP = System.getProperty("line.separator");


    /** */
    private static final Logger LOGGER = LogManager
        .getLogger(AlwaysTurnLeft.class);


    /** Set of maze rooms. */
    private transient Set<MazeRoom> roomSet;

    /** Maximum row possible on the given maze. */
    private transient int maxRow;
    /** Minimum column possible on the given maze. */
    private transient int minCol;
    /** Maximum column possible on the given maze. */
    private transient int maxCol;

    /** Current actual row. */
    private transient int currentRow;

    /**
     * Current relative column. We do not know yet the horizontal orientation so
     * negative column is accepted and adjusted later.
     */
    private transient int relativeCol;

    /**
     * This will generate contents of output file for submission.
     * 
     * @param args command line arguments.
     * 
     * @throws IOException if error occurs while parsing the file.
     */
    public static void main(final String... args) throws IOException
    {
        LOGGER.info("Program start. ");
        final Solution<?> solution = new AlwaysTurnLeft();
        solution.execute("c:\\");
        LOGGER.info("Program end. ");
    }


    /** {@inheritDoc} */
    @Override
    public String solve(final AlwaysTurnLeftBean caseBean)
    {
        this.maxRow = -1;
        this.minCol = 0;
        this.maxCol = 0;
        this.currentRow = -1;
        this.relativeCol = 0;

        this.roomSet = new HashSet<MazeRoom>();

        final char[] forward = caseBean.getForward().toCharArray();
        final Direction exit = processSteps(Direction.SOUTH, forward);
        final Direction secondEntry = aboutFace(exit);

        final char[] backward = caseBean.getBackward().toCharArray();
        processSteps(secondEntry, backward);
        adjustCoordOnExit(exit);

        assert this.maxCol - this.minCol + 1 > 0;
        return buildAnswer();
    }

    /**
     * @param initialDirection
     * @param steps
     */
    Direction processSteps(final Direction initialDirection,
            final char... steps)
    {
        Direction newDirection = initialDirection; //NOPMD: initial default, conditionally redefine.
        for (int i = 0; i < steps.length; i++) {

            final boolean insideMaze = i > 0;
            if (insideMaze && steps[i] == Move.Walk.getValue()) {
                final MazeRoom room = getRoom(this.relativeCol, this.currentRow);
                room.setCanWalk(newDirection);
            }

            switch (Move.fromChar(steps[i])) {
                case Walk:
                    adjustCoordOnMove(newDirection);
                    break;
                case Left:
                case Right:
                    newDirection = newDirection.turn(steps[i]);
                    break;
                default:
                    assert false : "Unexpected";
                    break;
            }
            this.maxRow = Math.max(this.maxRow, this.currentRow);
            this.minCol = Math.min(this.minCol, this.relativeCol);
            this.maxCol = Math.max(this.maxCol, this.relativeCol);
        }
        return newDirection;
    }


    /**
     * @param newDirection
     */
    void adjustCoordOnMove(final Direction newDirection)
    {
        if (newDirection == Direction.NORTH) {
            this.currentRow--;
        } else if (newDirection == Direction.EAST) {
            this.relativeCol++;
        } else if (newDirection == Direction.WEST) {
            this.relativeCol--;
        } else if (newDirection == Direction.SOUTH) {
            this.currentRow++;
        }
    }

    /**
     * @param face
     * @return
     */
    Direction aboutFace(final Direction face)
    {
        Direction retval;
        switch (face) {
            case NORTH:
                retval = Direction.SOUTH;
                break;
            case EAST:
                retval = Direction.WEST;
                break;
            case WEST:
                retval = Direction.EAST;
                break;
            case SOUTH:
                retval = Direction.NORTH;
                break;
            default:
                retval = face;
                assert false : "Unexpected";
                break;
        }
        return retval;
    }

    @SuppressWarnings({
            "PMD.AvoidInstantiatingObjectsInLoops",
            "PMD.DataflowAnomalyAnalysis" })
    String buildAnswer()
    {
        final int actualColLength = this.maxCol - this.minCol + 1;
        final char[][] chars = new char[this.maxRow + 1][actualColLength];

        for (final MazeRoom nextRoom : this.roomSet) {
            final int actualCol = nextRoom.getColumn() + Math.abs(this.minCol);
            chars[nextRoom.getRow()][actualCol] = nextRoom.getType();
        }

        final StringBuilder strBuilder = new StringBuilder();
        for (int i = 0; i <= this.maxRow; i++) {

            strBuilder.append(LINE_SEP);

            for (int j = 0; j < actualColLength; j++) {
                strBuilder.append(chars[i][j]);
            }
        }

        return strBuilder.toString();
    }


    /** {@inheritDoc} */
    @Override
    protected int getCaseUnitSize()
    {
        return 1;
    }


    /**
     * @param currentX
     * @param currentY
     * @return
     */
    private MazeRoom getRoom(final int currentX, final int currentY)
    {
        MazeRoom retval = null; //NOPMD: null default, conditionally redefine.        
        for (final MazeRoom nextRoom : this.roomSet) {
            if (nextRoom.getColumn() == currentX
                    && nextRoom.getRow() == currentY) {
                retval = nextRoom;
                break;
            }
        }
        if (retval == null) {
            retval = new MazeRoom(currentX, currentY);
            this.roomSet.add(retval);
        }

        return retval;
    }

    /** {@inheritDoc} */
    @Override
    protected AlwaysTurnLeftBean parseInputLines(final String... input)
    {
        final String[] param = input[0].split(" ");
        return new AlwaysTurnLeftBean(param[0], param[1]);
    }


    /**
     * @param exit
     */
    void adjustCoordOnExit(final Direction exit)
    {
        switch (exit) {
            case NORTH:
                break;
            case EAST:
                this.maxCol -= 1;
                break;
            case WEST:
                this.minCol += 1;
                break;
            case SOUTH:
                this.maxRow--;
                break;
            default:
                break;
        }
    }
}
